N/A
The present invention relates generally to SIMD array processors, and more particularly to SIMD array processors that can efficiently process multi-dimensional node meshes that are elongated in at least one coordinate direction.
Single-Instruction Multiple-Data (SIMD) array processors are known which comprise multi-dimensional arrays of interconnected Processing Elements (PE""s) executing the same instruction simultaneously on a plurality of different data samples. For example, a conventional SIMD array processor may include a two-dimensional xe2x80x9cNorth, East, West, and South (NEWS) arrayxe2x80x9d of PE""s. The PE""s of the NEWS array may be implemented on an Application Specific Integrated Circuit (ASIC) to simplify data I/O connections with dimensionally adjacent (xe2x80x9cneighboringxe2x80x9d) PE""s in the array. Further, the PE""s that are conceptually located along respective xe2x80x9cedgesxe2x80x9d of the two-dimensional NEWS array comprise suitable North, East, West, and South data I/O paths for connecting these PE""s with PE""s that are physically located on either the same ASIC or a different ASIC.
Such conventional SIMD array processors can be used to solve a set of partial differential equations with associated boundary conditions that describe the nature of a physical environment over a finite volume of space. For example, a particular set of partial differential equations and boundary conditions may be approximated by a corresponding set of finite difference equations that describe values of dependent variables at a finite number of points or xe2x80x9cnodesxe2x80x9d distributed within a problem space (commonly known as a xe2x80x9cnode meshxe2x80x9d). After assigning each processing element in the NEWS array to at least one node in the mesh, the SIMD array processor can be used to calculate the dependent variable values at the finite number of nodes.
One drawback of such SIMD array processors is that they are frequently inefficient at solving problems having elongated node geometry. For example, in problems involving models of electromagnetic wave propagation through long wave-guides or models of fluid flow through long conduits, the number of nodes in the mesh distributed along the transverse cross-sectional coordinate directions may be smaller than the number of PE""s in each coordinate direction of the NEWS array. As a result, when a node mesh for such a problem is mapped onto the NEWS array, communication distances between PE""s that perform processing for adjacent nodes may be long enough to significantly increase the time required to solve the problem. To avoid such long communication distances between PE""s, the node mesh may be mapped onto a rectangular subset of the NEWS array. However, when only a subset of the NEWS array is used, respective PE""s in the subset may be called upon to handle the processing for more nodes in the mesh. This can also significantly increase the time required to solve the problem.
It would therefore be desirable to have an SIMD array processor that can efficiently adapt itself to process multi-dimensional node meshes that are elongated in at least one coordinate direction. Such an SIMD array processor would efficiently process node meshes of varying geometry without switching data I/O connections between PE""s in the array.
In accordance with the present invention, an SIMD array processor is provided that can efficiently process multi-dimensional node meshes that are elongated in at least one coordinate direction. The SIMD array processor includes a plurality of small processor arrays interconnected to form a larger N-dimensional array. Each small processor array can access 2N data I/O paths which it can use to communicate with 2N other small processor arrays in the larger N-dimensional array. Each small processor array conceptually located at an interior point of the larger N-dimensional array can communicate with 2N dimensionally adjacent small processor arrays. Each processor array conceptually located at one (1) of at least one pair of dimensionally opposite boundaries of the larger N-dimensional array is communicably coupleable to fewer than 2N dimensionally adjacent small processor arrays and at least one small processor array conceptually located at the dimensionally opposing boundary.
Other features, functions, and aspects of the invention will be evident from the Detailed Description of the Invention that follows.